/*
 * @lc app=leetcode.cn id=4 lang=javascript
 *
 * [4] 寻找两个有序数组的中位数
 *
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
 *
 * algorithms
 * Hard (33.41%)
 * Total Accepted:    35.4K
 * Total Submissions: 105.9K
 * Testcase Example:  '[1,3]\n[2]'
 *
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 *
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 * 示例 1:
 *
 * nums1 = [1, 3]
 * nums2 = [2]
 *
 * 则中位数是 2.0
 *
 *
 * 示例 2:
 *
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 *
 * 则中位数是 (2 + 3)/2 = 2.5
 *
 *
 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  const merged = []
  let idx1 = 0
  let idx2 = 0
  while (idx1 < nums1.length || idx2 < nums2.length) {
    let n1
    if (idx1 < nums1.length) {
      n1 = nums1[idx1]
    }
    let n2
    if (idx2 < nums2.length) {
      n2 = nums2[idx2]
    }

    if (n1 === undefined) {
      merged.push(n2)
      idx2++
    } else if (n2 === undefined) {
      merged.push(n1)
      idx1++
    } else {
      if (n1 < n2) {
        merged.push(n1)
        idx1++
      } else {
        merged.push(n2)
        idx2++
      }
    }
  }
  if (merged.length % 2 === 0) {
    return (merged[merged.length / 2 - 1] + merged[merged.length / 2]) / 2
  }
  return merged[Math.floor(merged.length / 2)]
}
